import collections


class Solution(object):
    def getMaxRepetitions(self, s1, n1, s2, n2):
        """
        :type s1: str
        :type n1: int
        :type s2: str
        :type n2: int
        :rtype: int
        """
        m1 = len(s1)
        m2 = len(s2)
        index = 0
        cmt1 = 0
        cmt2 = 0
        pre = {0: (0, 0)}
        while True:
            for i in range(m1):
                if s1[i] == s2[index]:
                    index += 1
                    if index == m2:
                        cmt2 += 1
                        index = 0
            cmt1 += 1
            if index not in pre:
                pre[index] = (cmt1, cmt2)
            else:
                recmt_1 = cmt1 - pre[index][0]
                recmt_2 = cmt2 - pre[index][1]
                break
        pre_k1 = pre[index][0]
        pre_k2 = pre[index][1]
        re_k2 = ((n1 - pre_k1) // recmt_1) * recmt_2
        left_k1 = (n1 - pre_k1) % recmt_1
        for key in pre:
            if pre[key][0] - pre[index][0] == left_k1:
                left_k2 = pre[key][1] - pre[index][1]
                break
        k2 = pre_k2 + re_k2 + left_k2
        return k2 // n2




data = Solution()
s1 = "acb"
n1 = 4
s2 = "ab"
n2 = 2
print(data.getMaxRepetitions(s1, n1, s2, n2))
s1 = "acbacb"
n1 = 1
s2 = "acb"
n2 = 1
print(data.getMaxRepetitions(s1, n1, s2, n2))
s1 = "acbbac"
n1 = 100
s2 = "acbccabca"
n2 = 1
print(data.getMaxRepetitions(s1, n1, s2, n2))
s1 = "phqghumeaylnlfdxfircvscxggbwkfnqduxwfnfozvsrtkjprepggxrpnrvystmwcysyycqpevikeffmznimkkasvwsrenzkycxf"
n1 = 100
s2 = "xtlsgypsfa"
n2 = 1
print(data.getMaxRepetitions(s1, n1, s2, n2))
